package cn.arnold.tree;

// 顺序存储二叉树
// 需求：给你一个数组{1,2,3,4,5,6,7,8,9}， 要求以二叉树前序遍历的方式进行遍历
// 把数组映射成一个顺序存储二叉树
public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
        arrayBinaryTree.preOrder(0);
    }
}

// 顺序存储二叉树
class ArrayBinaryTree {
    private int[] array;    // 要转成顺序存储二叉树的数组

    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }

    /**
     * 前序遍历
     * @param index 数组的下标
     */
    public void preOrder(int index) {
        // 数组为空，则不遍历
        if (array == null || array.length == 0) {
            System.out.println("顺序存储二叉树为空....");
            return;
        }
        // 1. 输出当前元素
        System.out.println(array[index]);
        // 2. 左子树遍历
        if (2 * index + 1 < array.length) {
            preOrder(2 * index + 1);
        }
        // 3. 右子树遍历
        if (2 * index + 2 < array.length) {
            preOrder(2 * index + 2);
        }
    }
}
